Reception
| December 8 (Tuesday) | |||
| 19:00-21:00 | Welcome Reception, Sirius(51F) | ||
Program
Download: Program.pdf|
Day 1 (December 9) - ISAAC 2015 | |||
| Session A (Iris I) | Session B (Iris II) | ||
| 08:45-9:45 | Invited Talk 1: Soft Clustering: Models and Algorithms. Ravi Kannan / Chair: Kazuhisa Makino (Towers Ballroom) | ||
| 9:45-10:05 | Coffee Break | ||
|
10:05-11:45 Session 1 | Computational Geometry I / Sang Won Bae | Data Structures / Amr Elmasry | |
|
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino. Andrew Winslow | On the Succinct Representation of Unlabeled Permutations. Hicham El-Zein, Ian Munro and Siwei Yang | ||
|
Adaptive point location in planar convex subdivisions. Siu-Wing Cheng and Lau Man Kit | How to Select the Top k Elements from Evolving Data?. Qin Huang, Xingwu Liu, Xiaoming Sun and Jialin Zhang | ||
|
Competitive Local Routing with Constraints. Prosenjit Bose, Rolf Fagerberg, Andrè van Renssen and Sander Verdonschot | Optimal search trees with 2-way comparisons. Marek Chrobak, Mordecai J. Golin, J. Ian Munro and Neal E. Young | ||
|
Navigating Weighted Regions with Scattered Skinny Tetrahedra. Siu-Wing Cheng, Man Kwun Chiu, Jiongxin Jin and Antoine Vigneron | Multidimensional Range Selection. Timothy M. Chan and Gelin Zhou | ||
| 11:45-13:40 | Lunch | ||
|
13:40-14:55 Session 2 | Combinatorial Optimization and Approximation Algorithms I / Naonori Kakimura | Randomized Algorithms I / Rene Sitters | |
|
On the Minimum Cost Range Assignment Problem. Paz Carmi and Lilach Chaitman-Yerushalmi | The secretary problem with a choice function. Yasushi Kawase | ||
|
On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems. Sumedh Tirodkar and Sundar Vishwanathan | The Benefit of Recombination in Noisy Evolutionary Search. Tobias Friedrich, Timo Kötzing, Martin S. Krejca and Andrew M. Sutto | ||
|
General Caching Is Hard: Even with Small Pages. Lukáš Folwarczny and Jiří Sgall | Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples. Matthias Ernst, Maciej Liśkiewicz and Rüdiger Reischuk | ||
| 14:55-15:15 | Coffee Break | ||
|
15:15-16:30 Session 3 | Combinatorial Optimization and Approximation Algorithms II / Kei Kimura | Randomized Algorithms II / Shuji Kijima | |
|
Obtaining a Triangular Matrix by Independent Row-Column Permutations Guillaume Fertin, Irena Rusu and Stéphane Vialette | Heuristic time hierarchies via hierarchies for sampling distributions. Dmitry Itsykson, Alexander Knop and Dmitry Sokolov | ||
|
Many-to-one matchings with lower quotas: Algorithms and complexity. Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David Manlove and Jannik Matuschke | Unbounded Discrepancy of Deterministic Random Walks on Grids. Tobias Friedrich, Maximilian Katzmann and Anton Krohmer | ||
|
Minimizing the Maximum Moving Cost of Interval Coverage. Haitao Wang and Xiao Zhang | Trading off Worst and Expected Cost in Decision Tree Problems. Ferdinando Cicalese, Eduardo Laber and Aline Saettler | ||
|
Day 2 (December 10) - ISAAC 2015 | |||
| Session A (Iris I) | Session B (Iris II) | ||
| 08:45-9:45 | Invited Talk 2: Computing on Strategic Inputs. Constantinos Daskalakis / Chair: Khaled Elbassioni (Towers Ballroom) | ||
| 9:45-10:05 | Coffee Break | ||
|
10:05-11:45 Session 4 | Graph Algorithms and FPT I / Michael Lampis | Computational Geometry II / Sang Won Bae | |
|
Sliding Token on Bipartite Permutation Graphs. Eli Fox-Epstein, Duc Hoang, Yota Otachi and Ryuhei Uehara | Geometric Matching Algorithms for Two Realistic Terrains. Sang Duk Yoon, Min-Gyu Kim, Wanbin Son and Hee-Kap Ahn | ||
|
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Mamadou Moustapha Kanté, Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Sigve H. Saether and Yngve Villanger | Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability. Sándor Fekete, Robert Schweller and Andrew Winslow | ||
|
Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms. David Cattanéo and Simon Perdrix | The 2-center problem in a simple polygon. Eunjin Oh, Jean-Lou De Carufel and Hee-Kap Ahn | ||
|
Exact and FPT algorithms for Max-Conflict Free Coloring in Hypergraphs. Pradeesha Ashok, Sudeshna Kolay and Aditi Dudeja | Choice is Hard. Esther Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew Katz, Joseph Mitchell and Marina Simakov | ||
| 11:45-13:15 | Lunch | ||
|
13:15-14:55 Session 5 | Graph Algorithms and FPT II / Tsan-sheng Hsu | Computational Geometry III / Der-Tsai Lee | |
|
Fully Dynamic Betweenness Centrality. Matteo Pontecorvi and Vijaya Ramachandran | Minimizing the Diameter of a Spanning Tree for Imprecise Points. Chih-Hung Liu and Sandro Montanari | ||
|
When Patrolmen Become Corrupted: Monitoring a Graph using Faulty Mobile Robots. Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc and Najmeh Taleb | Model-based Classification of Trajectories. Maike Buchin and Stef Sijben | ||
|
Cops and Robbers on String Graphs. Tomáš Gavenčiak, Przemyslaw Gordinowicz, Vít Jelínek, Pavel Klavík and Jan Kratochvil | Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures. Elena Khramtcova and Evanthia Papadopoulou | ||
|
Min-Power Covering Problems. Eric Angel, Evripidis Bampis, Vincent Chau and Alexander Kononov | Unfolding Orthogonal Polyhedra with Linear Refinement. Yi-Jun Chang and Hsu-Chun Yen | ||
| 14:55-15:15 | Coffee Break | ||
|
15:15-16:30 Session 6 | Combinatorial Optimization and Approximation Algorithms III / Rene Sitters | Randomized Algorithms III / Shuji Kijima | |
|
Colored Non-Crossing Euclidean Steiner Forest. Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff | Generating Random Hyperbolic Graphs in Subquadratic Time. Moritz von Looz, Henning Meyerhenke and Roman Prutkin | ||
|
On a generalization of Nemhauser and Trotter's local optimization theorem. Mingyu Xiao | Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing. Stefan Funke and Sabine Storandt | ||
|
Approximation Algorithms in the Successive Hitting Set Model. Sabine Storandt | Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty. Andrew Mastin, Patrick Jaillet and Sang Chin | ||
| 19:00-21:00 | Banquet(Towers Ballroom) | ||
|
Day 3 (December 11) - ISAAC 2015 | |||
| Session A (Iris I) | Session B (Iris II) | ||
| 08:45-9:45 | Invited Talk 3: Lower bounds on the size of linear programs. Thomas Rothvoss / Chair: Kazuhisa Makino (Towers Ballroom) | ||
| 9:45-10:05 | Coffee Break | ||
|
10:05-11:45 Session 7 | Computational Geometry IV / Chan-Su Shin | Complexity and Quantum Computation I / Michal Koucky | |
|
An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings. Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer, Alexander Pilz and Manuel Wettstein | Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof. Jun Yan | ||
|
Improved approximation for Frechet distance on c-packed curves matching conditional lower bounds. Karl Bringmann and Marvin Künnemann | Effectiveness of Structural Restrictions for Hybrid CSPs. Vladimir Kolmogorov, Michal Rolinek and Rustem Takhanov | ||
|
Computing the Gromov-Hausdorff Distance for Metric Trees. Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos and Yusu Wang | Polynomial-time isomorphism test of groups that are tame extensions (Extended Abstract). Joshua Grochow and Youming Qiao | ||
|
The VC-Dimension of Visibility on the Boundary of a Simple Polygon. Matt Gibson, Erik Krohn and Qing Wang | Quantum Algorithm for Triangle Finding in Sparse Graphs. Shogo Nakajima and Francois Le Gall | ||
| 11:45-13:15 | Lunch | ||
|
13:15-14:55 Session 8 | Graph Drawing & Planar Graphs / Seokhee Hong | Complexity and Quantum Computation II / Valia Mitsou | |
|
On Hardness of the Joint Crossing Number. Petr Hlineny and Gelasio Salazar | A New Approximate Min-Max Theorem with Applications in Cryptography. Maciej Skorski | ||
|
An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs. Diptarka Chakraborty and Raghunath Tewari | Give Me Another One!. Mike Behrisch, Miki Hermann, Stefan Mengel and Gernot Salzer | ||
|
Constant Query Time (1+ε)-Approximate Distance Oracle for Planar Graphs. Qian-Ping Gu and Gengchun Xu | On the Complexity of Computing Prime Tables. Martin Farach-Colton and Meng-Tsung Tsai | ||
|
Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions. Martin Nölenburg, Roman Prutkin and Ignaz Rutter | Game values and computational complexity: An analysis via black-white combinatorial games. Stephen Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer and Thomas Thierauf | ||
| 14:55-15:15 | Coffee Break | ||
|
15:15-16:55 Session 9 | Online and Streaming Algorithms / Yasushi Kawase | String and DNA Algorithms / Michal Koucky | |
|
Run Generation Revisited: What Goes Up May or May Not Come Down. Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh and Hoa T. Vuf | An In-place Framework for Exact and Approximate Shortest Unique Substring Queries. Wing-Kai Hon, Sharma V. Thankachan and Bojian Xu | ||
|
Streaming Verification in Data Analysis. Samira Daruki, Justin Thaler and Suresh Venkatasubramanian | Inferring Strings from Full Abelian Periods. Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda | ||
|
All-Around Near-Optimal Solutions for the Online Bin Packing Problem. Shahin Kamali and Alejandro Lopez-Ortiz | Toehold DNA Languages are Regular. Sebastian Brandt, Nicolas Mattia, Jochen Seidel and Roger Wattenhofer | ||
|
Serving Online Requests with Mobile Servers. Abdolhamid Ghodselahi and Fabian Kuhn | |||
Contact:
isaac2015@is.nagoya-u.ac.jp